/* 
 * CMPS 258: Programming Languages
 *        Assignment 2 - Part2: "Spy" - March 24, 2008
 *        Group name: Doomsday
 *        Authors:  Ramsey Nasser (ID# 200600496) 
 *                  Hadi Abu Rislan (ID# 200600426) 
 *                  Kevin Azzam (ID# 200602033)
 * 
 * Implementation of graph data structure and related functions.
 * 
 * For the sake of maintainability, function documentation is not repeated
 * here. For a description of the intent and usage of each function, refer to
 * the header file (graph.h) 
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "graph.h"
#include "path.h"
#include "util.h"



graph* graph_init(GRAPH_TYPE type) {
	graph* g;
	allocate(g,sizeof(graph))
	
	g->type = type;
	g->vert_count = 0;
	g->edge_count = 0;
	g->verts = NULL;
	g->edges = NULL;
	
	return g;
}

int graph_add_vert(graph* g) {
	vertex* new_vert;
	
	// Grow the list of verts
	allocateg(g->verts,g->vert_count);
	
	// Point to the new vertex
	new_vert = &g->verts[g->vert_count-1];
	// Keep the vertex's id in synch with its index in the graph's vertex list
	new_vert->id = g->vert_count-1;
	
	return new_vert->id;
}

int* graph_add_verts(graph* g, int n) {
	int i;
	int* vertex_ids;
	
	allocate(vertex_ids,sizeof(int) * n);
	
	for(i=0;i<n;i++)
		vertex_ids[i] = graph_add_vert(g);
	
	return vertex_ids;
}

void graph_connect_verts(graph* g, int v1, int v2) {
	vertex* vert1 = &g->verts[v1];
	vertex* vert2 = &g->verts[v2];
	edge* new_edge;
	
	// Grow the graph's edge list
	allocateg(g->edges,g->edge_count);
	new_edge = &g->edges[g->edge_count-1];
	// Make edge from v1 to v2
	new_edge->from = vert1;
	new_edge->to = vert2;
	
	// If graph is undirected, do the same in the other direction 
	if(g->type == GRAPH_UNDIRECTED) {
		allocateg(g->edges,g->edge_count);
		new_edge = &g->edges[g->edge_count-1];
		new_edge->from = vert2;
		new_edge->to = vert1;
	}
}

int graph_are_connected(graph* g, int v1, int v2) {
	int i;
	int con12 = FALSE; // Connected from v1 to v2
	int con21 = FALSE; // Connected from v2 to v1
	
	if(v1==v2)
		return TRUE;
	
	// Loop through edge list and check for connectivity in both directions
	for(i=0;i<g->edge_count;i++)
		if(g->edges[i].from->id == v1 && g->edges[i].to->id == v2)
			con12 = TRUE;
		else if(g->edges[i].from->id == v2 && g->edges[i].to->id == v1)
			con21 = TRUE;
	
	if(g->type == GRAPH_UNDIRECTED)
		return con12 && con21;
	else if(g->type == GRAPH_DIRECTED)
		return con12;
	else
		return FALSE;
}

edge* graph_get_edge(graph* g, int v1, int v2) {
	int i;
	for(i=0;i<g->edge_count;i++) {
		if(g->edges[i].from->id == v1 && g->edges[i].to->id == v2) {
			return &g->edges[i];
		}
	}
			
	return NULL;
}

void graph_print(graph* g) {
	int i;
	char* conn;
	
	if(g->type == GRAPH_DIRECTED)
		conn = "-->";
	else if(g->type == GRAPH_UNDIRECTED)
		conn = "<->";
	
	printf("graph at 0x%X {\n",(unsigned int)g);
	// Print every vertex in the graph
	for(i=0;i<g->vert_count;i++)
		printf("    %d;\n",i);
	
	// Print every edge in the graph
	for(i=0;i<g->edge_count;i++)
		printf("    %d %s %d;\n",g->edges[i].from->id,conn,g->edges[i].to->id);
			
	printf("}\n");
}

void graph_get_all_paths(graph* g, int v1, int v2, path** paths, int* paths_size, path* p) {
	int i;
	path* local_path; // The path for this function call
	
	if(!p) {
		// Initial call, create path to pass down
		local_path = path_init(g,v1);
	} else {
		// Subsequent calls, clone passed down path
		local_path = path_clone(p);
		path_append(local_path,v1);
	}
	
	if(v1 == v2) {
		// We reached the end
		paths[*paths_size] = local_path;
		*paths_size += 1;
	}
	
	// Preform DFS
	for(i=0;i<g->edge_count;i++)
		if(g->edges[i].from->id == v1 && !path_contains(local_path,g->edges[i].to->id))
			graph_get_all_paths(g, g->edges[i].to->id, v2, paths, paths_size, local_path);
}

void graph_free(graph* g) {
	free(g->verts);
	free(g->edges);
	free(g);
}
